package Sort.sort;

//�������򣬲��ȶ����򣬺±���Ƶ���ⷽ�����Ż��㷨
public class QuickSort {

    public static void main(String[] args) {
        int[] array = {9, 2, 1, 0, 5, 4, 3};
        quickSort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
        }

    }

    public static void quickSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        quickSort(array, 0, array.length - 1);
    }

    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pos = partition(array, low, high);
            quickSort(array, low, pos - 1);
            quickSort(array, pos + 1, high);
        }
    }

    public static int partition(int[] array, int low, int high) {
        int key = array[low];
        while (low < high) {
            while (low < high && array[high] >= key) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= key) {
                low++;
            }
            array[high] = array[low];
        }
        array[high] = key;
        return high;
    }


}
